1. Field of the Invention
This invention relates to data communications and, more particularly, to a crossbar packet data switch having an improved scheduling mechanism.
2. Background Description
The provision of high speed switching devices is vital to modern packet switched data communications systems, such as those based on Asynchronous Transfer Mode (ATM) technology.
Many types of switching architectures have been proposed and/or implemented in high speed switches. A general review of such architectures can be found in TOBAGI `Fast Packet Switch Architectures for Broadband Integrated Services Digital Networks` Proc IEEE Vol 78, No 1, pp 133-167, (1990).
In space division type switch architectures, such as those based on crossbar switch matrices, multiple concurrent paths are established from a plurality of inputs to a plurality of outputs, each path only being required to operate at the same data rate as an individual input or output line. One problem with this type of switch architecture is that it is generally not possible for all the required paths from each input to each output to be set simultaneously. This has the result that if two data packets arrive simultaneously at the same input and/or destined for the same output then the passage of such data packets through the switch has to be scheduled so that one of the packets must wait in some kind of buffer or queue.
Various types of queuing and buffering arrangements have been proposed, examples of which can be found in the above mentioned article. A key factor in the design of such arrangements is to balance the requirement for maximum switch throughput and to ensure that the scheduling of the switching paths is fair in the sense that, whatever the input traffic pattern, the amount of traffic allowed to pass through any particular input-output path must receive at least a defined share of the bandwidth on the respective input or output path. This is particularly important in the presence of ATM non-reserved bandwidth (NRB) traffic which can be extremely bursty.
US-A-5267235 and US-A-5500858 describe scheduling arrangements for space-division switches which provide a match between requesters, ie the input adapters of a switch, that must arbitrate for service from one of a number of servers, ie the output adapters of a switch. Each requester presents a set of requests. Requests are presented to all servers to which access is desired. Each server selects one such request and asserts a response signal stating the request selected. Each requester then selects one incoming grant response and deasserts requests to any other servers. In US-A-5267235 it is proposed that the servers select requests on a random or pseudo-random basis. US-A-5500858 proposes a rotating priority approach for selection of requests by the servers and subsequently of a grant response by the requesters.
US-A-5199028 describes a cross point switching array in which a very short queue is provided at each cross point of the switching matrix in order to prevent blocking when more than one input port wishes to send a packet to the same output port at the same time. Packets are loaded from an input queue into the crosspoint queue. A rotating priority output mechanism is used to transfer packets from the crosspoint queues to output ports. This arrangement, however, has less than optimal throughput because at any particular time packets whose input-output path is available at that time may be blocked in the queue by packets higher in the queue whose input-output path is not available -a problem commonly referred to in the art as head of line blocking.
US-A-5392401 describes a switch in which, at each input, there is one input queue per output target. A scheduling mechanism is used in order to select the queue in each input adapter with the rule that, in any given cell time, each input can only send to one output at a time and each output can only receive from one input. Such a structure is relatively simple to implement, but suffers from the drawback that the scheduling algorithm is difficult to optimize.